1. Field of the Invention
The present invention is a method of controlling access to the call completion on busy link service in a private telecommunication network.
2. Description of the Prior Art
The invention concerns private telecommunication networks. Such networks are formed of communication nodes connected together by links carrying calls and/or signaling. It applies equally to physical private networks (which are formed of dedicated connections), virtual private networks and hybrid networks combining the two solutions. In the remainder of the description the invention is described with reference to one example of a private network with signaling, but it applies more generally to other private networks.
The Dijkstra algorithm is described in the literature on algorithms and calculates the shortest path between tow nodes in a graph. In operation, the algorithm considers a graph G with N nodes, which is valued, i.e., each existing path of which between two nodes i and j is assigned a value or weight I(i,j); considers an outgoing node s of the graph G and an incoming node d; and seeks a path minimizing Π (s,d), the distance from s to d, i.e., the sum of the values of the connections s to d. S is the subgraph of G formed of the nodes x for which the minimum path to s is known, and {overscore (S)} is its complement. xcex93I is the set of nodes adjoining a given node i.
Initially the subgraph S contains only the node s, and {overscore (S)} contains all the other nodes, assigned the following initial values:
xcfx80(s, i)=l(s, i) for i ∈xcex93s, the parent node being s;
xcfx80(s, d)=∞, for the other nodes, which have no parent node.
An iteration of the algorithm is effected in the following manner.
If {overscore (S)} is empty, or if it contains only nodes i with xcfx80(s, i)=∞, the algorithm has finished.
Otherwise, the node n of {overscore (S)} is considered which is nearest the originating node, i.e. the node which minimizes xcfx80(s, i), i ∈ {overscore (S)}; this node is taken from {overscore (S)} and placed in S.
The nodes adjacent this node n are then considered and the algorithm calculates
xcfx80(s, n)=l(n, j),j∈xcex93n and j∈{overscore (S)}; 
If this quantity is less than xcfx80(s, j), then xcfx80(s, j) is updated:
xcfx80(s, j):=xcfx80(s, n)+l(n, j) 
and the parent node of is also updated, which becomes n.
This operation is carried out for all the nodes of xcex93n, after which {overscore (S)} is reordered.
In this way, all the nodes of the graph are progressively added to S, in order of increasing path length. To find a path to a given node d, the algorithm can be interrupted before it finishes, since the destination node a has been added to the subgraph S.
The validity of the algorithm is demonstrated by the following reductio ad absurdum argument. Consider the node n nearest {overscore (S)} which must be added to S. If there is a nearer path, that path starts from s and arrives at n and has a first node m in {overscore (S)}. Then:
xcfx80(s, m)+xcfx80(m, n) less than xcfx80(s, n) 
and, since xcfx80(m, n) is positive or zero:
xcfx80(s, m) less than p(s, n) 
which contradicts the hypothesis. It is also clear that xcfx80(s, m) has been calculated in a preceding iteration, when adding the parent of m to S.
The document by J. Eldin and K. P. Lathia xe2x80x9cLe RNIS appliquxc3xa9 au Centrex et au rxc3xa9seaux privxc3xa9s virtuelsxe2x80x9d [The ISDN applied to Centrex and to virtual private networks] contains a description of physical private networks and virtual private networks. As explained in the document, in a physical private network the various sites or nodes are connected by dedicated circuits but in a virtual private network each node is connected to the local switch nearest the public network, where appropriate software sets up the connections on demand. There are two variants of the virtual private network: on the one hand, semi-permanent connections can be provided, which are set up without dialing as soon as any of the nodes requires the circuit, and which always connect the same two points. Such may be the case in particular for signaling connections in an application on an integrated services digital network. On the other hand, switched connections can be provided, which can be set up only by dialing.
The remainder of the description considers only physical or virtual private networks formed of nodes connected by links, which can be of any type: dedicated connections, or links using an external network; the latter can be of any typexe2x80x94the public switched network, a public land mobile network, an integrated services digital network, etc. FIG. 1 shows one example of a private network of this kind. This network includes, for example, nodes 1 to 6; nodes 1, 2 and 4 to 6 are connected to the public network 8 by circuit groups 11, 12 and 14 to 16. The nodes are interconnected by links formed of private connections, shown in bold in the figure, or, as in the case of the link between nodes 5 and 6, by a link comprising only a signaling connection. For a digital link, each private connection comprises at least one access, formed by a signaling connection and a plurality of B channels. The link between nodes 5 and 6 in FIG. 1, and likewise the link between nodes 1 and 2, comprises a signaling connection and no B channel; this is typical of a node corresponding to a branch office, for which the volume of traffic is not very high.
The problem of overflow, i.e. the problem of a call request that cannot be satisfied by the network because its resources are congested, arises in private networks. This problem can arise if the private links of the private network have a fixed capacity, rather than a capacity which is allocated dynamically and which is less than the possible maximum volume of traffic. Completing the corresponding call using the public network is known in itself. In other words, if a user at node 2 wants to contact a user at node 6, and if the private network is congested and cannot complete the call, the call is completed via circuit groups 12 and 16 and the public network. This can be the case, for example, if the connection between nodes 2 and 4 is congested. In FIG. 1, reference numeral 10 shows schematically a call of this kind via the public network. Overflow may also be necessary if the link in question has no B channel, as in the case of node 6 in FIG. 1.
One problem is the cost of such overflows. Because of this cost, rules can be defined denying certain users or certain categories of user access to this service.
The prior art also provides a CCBL (call completion on busy link) service which provides automatic callback if a link of the private network is busy or congested. In this case, the calling user is put on hold for as long as the private network link is congested and is called back when sufficient resources are released to route the call. In existing private networks this CCBL service is provided without distinguishing between users.
This solution gives rise to the following problem in the case of overflows to the public network. If an overflow is necessary to reach the called user, and if the rights or monitored cost of the user are less than the charge incurred for the overflow, the CCBL service might never call back. This is the case in particular for users who have no overflow rights. The CCBL request therefore remains unsatisfied.
The invention proposes a solution to this new problem. It prevents users being queued unnecessarily and prevents congestion of the private network by CCBL requests that cannot be satisfied. The invention applies particularly to the routing solution proposed in our application filed the same day as this application with the title xe2x80x9cRouting of calls with overflow in a private networkxe2x80x9d. It also applies to routes chosen by a separate process and which enables one or more overflows to a public network.
To this end, the invention proposes a method of controlling access to the call completion on busy link service in a private telecommunication network allowing overflow to another network, wherein users are allocated rights to overflows and access to the service by a user for a call entailing at least one overflow is dependent on the rights of the user.
In one embodiment of the method some users do not have the right to overflows and access to the service for a call entailing at least one overflow is refused to such users.
A step of calculating the minimum number of overflows for a call can be provided, advantageously using the Dijkstra algorithm.
In one embodiment of the method certain links are not monitored, certain users do not have rights to overflows except on said links which are not monitored and access to the service for a call entailing at least one overflow onto an unmonitored link is refused to such users.
A step of calculating the minimum number of overflows onto monitored links for a call can be provided, advantageously using the Dijkstra algorithm.
In another embodiment of the invention access to the service by a user for a call entailing at least one overflow depends on a comparison of the rights of the user and the cost of the overflow(s).
The method preferably comprises a step of calculating the minimum cost of the overflows for a call, preferably using the Dijkstra algorithm.
A connectivity flag can then be propagated during application of the Dijkstra algorithm to determine if there is a path without overflows.
Other features and advantages of the invention will become apparent on reading the following description of embodiments of the invention, which is given by way of example and with reference to the accompanying drawings.